package com.note.feng.leetcode.algorithms.easy.six;

import java.util.ArrayList;
import java.util.List;

public class SixHundredNinetySix {
    /**
     * 696 计数二进制子串
     * 给定一个字符串 s，统计并返回具有相同数量 0 和 1 的非空（连续）子字符串的数量，
     * 并且这些子字符串中的所有 0 和所有 1 都是成组连续的。
     *
     * 重复出现（不同位置）的子串也要统计它们出现的次数。
     *  
     * 示例 1：
     *
     * 输入：s = "00110011"
     * 输出：6
     * 解释：6 个子串满足具有相同数量的连续 1 和 0 ："0011"、"01"、"1100"、"10"、"0011" 和 "01" 。
     * 注意，一些重复出现的子串（不同位置）要统计它们出现的次数。
     * 另外，"00110011" 不是有效的子串，因为所有的 0（还有 1 ）没有组合在一起。
     * 示例 2：
     *
     * 输入：s = "10101"
     * 输出：4
     * 解释：有 4 个子串："10"、"01"、"10"、"01" ，具有相同数量的连续 1 和 0 。
     *  
     * 提示：
     *
     * 1 <= s.length <= 105
     * s[i] 为 '0' 或 '1'
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/count-binary-substrings
     */
    /**
     * 解法：
     * 先统计出连续相同字符出现的次数，用 list 存储，
     * list 中两个相邻的数一定代表两种不同的字符出现的次数，
     * 它们能组成的满足条件的子串数目为 它们的最小数，
     * 即一对相邻数对答案的贡献。
     * 遍历 list ，计算出相邻两个数的贡献，再求和就是答案。
     * @param s
     * @return
     */
    public int countBinarySubstrings(String s) {
        int res = 0,left = 0,n = s.length();
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i < n; i++) {
            if(s.charAt(i) != s.charAt(i - 1)){
                list.add(i - left);
                left = i;
            }
        }
        list.add(n - left);
        for (int i = 1; i < list.size(); i++) {
            res += Math.min(list.get(i), list.get(i - 1));
        }
        return res;
    }
}
